package cn.hy.today;

class Solution_2182 {


    /**
     * 每次选择当前剩余的字典序最大的字符加到字符串末尾；如果字符串末尾的字符已经连续出现了 repeatLimit
     * 次，则将字典序次大的字符加到字符串末尾，随后继续选择当前剩余的字典序最大的字符加到字符串末尾，
     * 直至使用完字符或没有新的字符可以合法加入。
     */
    public String repeatLimitedString(String s, int repeatLimit) {
        int n = 26;
        int[] count = new int[n];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        StringBuilder ret = new StringBuilder();
        int m = 0; // 当前统计的字符个数
        for (int i = n - 1, j = n - 2; i >= 0 && j >= 0; ) {
            if (count[i] == 0) { //当前字符已经填完，填入后面的字符，重置 m
                m = 0;
                i--;
            } else if (m < repeatLimit) { // 当前字符未超过限制
                count[i]--;
                ret.append((char) ('a' + i));
                m ++;
            } else if (j >= i || count[j] ==0 ) { // 当前字符已经超过限制，查找可填入的其他字符
                j--;
            } else { //  当前字符已经超过限制，填入其他字符，并且重置 m
                count[j]--;
                ret.append((char) ('a' + j));
                m = 0; // 说明后面还是填入 i 所在的的字符
            }
        }
        return ret.toString();
    }
}